<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>1129. 颜色交替的最短路径</title>
  </head>
  <body>
    <script>
      //     在一个有向图中，节点分别标记为 0, 1, ..., n-1。图中每条边为红色或者蓝色，且存在自环或平行边。

      // red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。

      // 返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

      //

      // 示例 1：

      // 输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
      // 输出：[0,1,-1]
      // 示例 2：

      // 输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
      // 输出：[0,1,-1]
      // 示例 3：

      // 输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
      // 输出：[0,-1,-1]
      // 示例 4：

      // 输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
      // 输出：[0,1,2]
      // 示例 5：

      // 输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
      // 输出：[0,1,1]
      //

      // 提示：

      // 1 <= n <= 100
      // red_edges.length <= 400
      // blue_edges.length <= 400
      // red_edges[i].length == blue_edges[i].length == 2
      // 0 <= red_edges[i][j], blue_edges[i][j] < n

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
      /**
       * @param {number} n
       * @param {number[][]} redEdges
       * @param {number[][]} blueEdges
       * @return {number[]}
       */
      var shortestAlternatingPaths = function (n, redEdges, blueEdges) {
        const map = Array.from({ length: n }, () => [])
        for (const [f, t] of red_edges) {
          map[f].push(t)
        }
        for (const [f, t] of blue_edges) {
          map[f].push(t | 128)
        }
        const ans = new Array(n).fill(-1)
        const vis = new Set()
        let queue = [0, 128]
        let step = -1
        while (queue.length) {
          const tmp = []
          step++
          for (const f of queue) {
            vis.add(f)
            const idx = f & -129
            if (ans[idx] === -1) ans[idx] = step
            for (const t of map[idx]) {
              if (vis.has(t)) continue
              // 同色
              if ((f & 128) === (t & 128)) continue
              tmp.push(t)
            }
          }
          queue = tmp
        }
        return ans
      }
    </script>
  </body>
</html>
